﻿using System;

class MaximalSum
{
    static void Main()
    {
        int[,] array = {                          
          {7, -16, 33, -23, 2, 1, 12, 9},
          {10, 3, 19, -8, 5, 6, 44, -20},
          {14, 6, 7, 19, 14, -13, 5, 19},
          {-16, 30, 9, 4, 25, -12, 8, 2},
          {14, 15, 17, 9, -1, 0, 81, -7}
        };

        PrintMatrix(array);

        // Finding the maximal 3x3 submatrix
        int maxSum = 0;
        int tempSum = 0;
        int[,] maxSubMatrix = new int[3, 3];

        for (int row = 0; row < array.GetLength(0) - 2; row++)
        {
            for (int col = 0; col < array.GetLength(1) - 2; col++)
            {
                tempSum = CalculateSubMastrix(array, row, col);

                // If the current sum is bigger than the maximal one we fill the maxArray with new values
                if (tempSum > maxSum)
                {
                    maxSum = tempSum;
                    UpdateMaxArray(maxSubMatrix, array, row, col);
                }

                tempSum = 0;
            }
        }

        // Printing the submatrix with the biggest 3x3 sum of its elements
        Console.WriteLine();
        Console.WriteLine("The maximal sum is: " + maxSum);
        Console.WriteLine("The maximal submatrix is:" );

        PrintMatrix(maxSubMatrix);
    }

    private static void PrintMatrix(int[,] array)
    {
        for (int row = 0; row < array.GetLength(0); row++)
        {
            for (int col = 0; col < array.GetLength(1); col++)
            {
                Console.Write("{0,3}", array[row, col]);
            }
            Console.WriteLine();
        }
    }

    private static void UpdateMaxArray(int[,] maxSubMatrix, int[,] array, int row, int col)
    {
        for (int subRow = row, maxRow = 0; subRow < row + 3; subRow++, maxRow++)
        {
            for (int subCol = col, maxCol = 0; subCol < col + 3; subCol++, maxCol++)
            {
                maxSubMatrix[maxRow, maxCol] = array[subRow, subCol];
            }
        }
    }

    private static int CalculateSubMastrix(int[,] array, int row, int col)
    {
        int result = 0;

        for (int subRow = row; subRow < row + 3; subRow++)
        {
            for (int subCol = col; subCol < col + 3; subCol++)
            {
                result += array[subRow, subCol];
            }
        }
        return result;
    }
}